#include<stdio.h>
#define MAX 30001
#define MAXLONG 1000000
#define FILEINP "CENTRE.INP"
#define FILEOUT "CENTRE.OUT"
long n,m,d[MAX]={0},i;
int a[MAX][MAX],trace[MAX][MAX],free[MAX];
void input(){
     FILE *fp=fopen(FILEINP,"r");
     fscanf(fp,"%ld%ld",&n,&m);
     for(i=1;i<=m;i++){
        fscanf(fp,"%ld%ld%ld",&u,&v,&c);
        a[u][v]=a[v][u]=c;
    }
    for(i=0;i<=n;i++)d[i]=MAXLONG;
    fclose(fp);
}
void createB(){
    int u,v;
    do{
        u=0;
        for(i=1;i<=n;i++)
            if(!free[i] && d[i]<d[u])u=i;
        if(u==0)break;
        free[u]=1;
        for(v=1;v<=n;v++){
            if(!free[v] || d[v]>d[u]+c[u][v])continue;
            if(d[v]<d[u]+c[u][v])trace[v][0]=1;
            else trace[v][0]++;
            trace[v][trace[v][0]]=u;
            d[v]=d[u]+c[u][v];
        }
    }while(1);
}
int main(){
    input();
    createB();
    return 0;
}
